package jun;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-6-12 9:28
 * @description：
 * @modified By：
 * @version:
 */
public class Jun12 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/ 188. 买卖股票的最佳时机 IV
     * create time: 2020-6-12 9:29
     * @params [k, prices]
     * @return int
     */
    public int maxProfit(int k, int[] prices) {
        if(prices.length==0){
            return 0;
        }
        if (k > prices.length/ 2)
            return maxProfit_k_inf(prices);
        //0没有交易 1第一次买入 2第二次买入
        int[][][] dp = new int[prices.length+1][k+1][2];
        //回来看下初始化怎么办
        for (int i = 0; i <= prices.length; i++) {
            dp[i][0][0] = 0;//至今为止没有交易，收益为0
            dp[i][0][1] = Integer.MIN_VALUE;//交易了0次，但持有股票，不符合规则
            for (int j = 1; j <= k; j++) {
                if(i==0){
                    dp[i][j][0] = 0;//第一天买入t次，当天卖出t次,收入为0
                    dp[i][j][1] = -prices[i];//甭管第一天买多少次，反正最后少卖一次，持有了股票
                    continue;
                }
                dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]);//第i天有两次买入持有股票 两种选择 上一天有两次买入持有股票 或者上一天有一次买入并且没有持有股票买入当天的股票
                dp[i][j][0] = Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]);
            }
        }
        return dp[prices.length][k][0];
    }
    int maxProfit_k_inf(int[] prices) {
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
        }
        return dp_i_0;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/continuous-subarray-sum/ 523. 连续的子数组和
     * create time: 2020-6-12 10:38
     * @params [nums, k]
     * @return boolean
     */
    public boolean checkSubarraySum(int[] nums, int k) {
        int len = nums.length;
        int[] dp = new int[len];
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
        }
        if (len <= 1) {
            return false;
        }
        if (sum == 0) {
            return true;
        }
        dp[0] = nums[0];
        for (int i = 1; i < len; i++) {
            dp[i] = dp[i - 1] + nums[i];
        }
        for (int i = 1; i < len; i++) {
            if (k == 0) {
                if (dp[i] == 0) {
                    return true;
                }
            } else {
                if (dp[i] % Math.abs(k) == 0) {
                    return true;
                }
            }
        }

//二维数组的dp[i,j] 用nums[j]-nums[i-1]代替
        for (int i = 1; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (k == 0) {
                    if ((dp[j] - dp[i - 1] == 0) && i != j) {
                        return true;
                    } else {
                        continue;
                    }
                } else {
                    if ((((dp[j] - dp[i - 1]) % Math.abs(k) == 0) && i != j)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    /**
     *
     * https://leetcode-cn.com/problems/can-i-win/solution/hui-su-zhuang-ya-dp-by-8bun/
     * 记忆化回溯（也称为递归+备忘录），自顶向下
     * 采用记忆化后的时间复杂度为O(2^n)(如果不进行记忆的话，时间复杂度将是O(n!))，可以理解为已经缩成了只有一个分支了
     * 然后为什么要进行记忆化：
     * 因为我们发现，例如[2,3]和[3,2]之后的玩家选择状态都是一样的，都是可以从除了2,3之外的
     * 数字进行选择，那么就可以对选择2和3后第一个玩家能不能赢进行记忆存储
     * 这里采用state[]数组存储每个数字是否都被选过，选过则记录为1，然后我们将state.toString()
     * 使得[2,3]和[3,2]它们的结果都是一样的"0011"，作为key，存储在HashMap中，value是选了2和3
     * 之后第一个玩家是否稳赢
     * @param maxChoosableInteger
     * @param desiredTotal
     * @return
     */
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false; //1,..maxChoosable数列总和都比目标和小
        int[] state = new int[maxChoosableInteger + 1];  //state[1]=1表示1被选了

        return backtraceWitMemo(state, desiredTotal, new HashMap<String, Boolean>());
    }

    private boolean backtraceWitMemo(int[] state, int desiredTotal, HashMap<String, Boolean> map) {
        String key = Arrays.toString(state); //这里比较关键，如何表示这个唯一的状态，例如[2,3]和[3,2]都是"0011"，状态一样
        if (map.containsKey(key)) return map.get(key);  //如果已经记忆了这样下去的输赢结果,记忆是为了防止如[2,3]，[3,2]之后的[1,4,5,..]这个选择区间被重复计算

        for (int i = 1; i < state.length; i++){
            if (state[i] == 0){ //如果这个数字i还没有被选中
                state[i] = 1;
                //如果当前选了i已经赢了或者选了i还没赢但是后面对方选择输了
                if (desiredTotal - i <= 0 || !backtraceWitMemo(state, desiredTotal - i, map)) {
                    map.put(key, true);
                    state[i] = 0; //在返回之前回溯
                    return true;
                }
                //如果不能赢也要记得回溯
                state[i] = 0;
            }
        }
        //如果都赢不了
        map.put(key, false);
        return false;
    }

}
